package Algorithm.Dp;

import java.util.TreeSet;

//https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/
//363. 矩形区域不超过 K 的最大数值和
public class Leetcode_363_notice_max_sumof_rectangle_nolarger_than_k {
    /**
     * 关键在于在一维上怎么解决最大不大于k的最大数值和
     */
    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            int ans = Integer.MIN_VALUE;
            int m = matrix.length, n = matrix[0].length;
            for(int i = 0; i<m;i++){
                int[] sum = new int[n];
                for(int j=i;j<m;j++){
                    for(int c=0;c<n;c++){
                        sum[c] += matrix[j][c];
                    }

                    TreeSet<Integer> sumSet = new TreeSet();
                    sumSet.add(0);
                    int s = 0;
                    for(int v : sum){
                        s += v;
                        Integer ceil = sumSet.ceiling(s - k);
                        if(ceil != null){
                            ans = Math.max(ans, s - ceil);
                        }
                        sumSet.add(s);
                    }
                }
            }
            return ans;
        }
    }
}
